package com.fw.leetcode.linkedlist;

import com.fw.leetcode.LeetCode;

/**
 * 82. Remove Duplicates from Sorted List II
 *
 * Given the head of a sorted linked list, delete all nodes that have duplicate numbers,
 * leaving only distinct numbers from the original list.
 * Return the linked list sorted as well.
 *
 * Example 1:
 *  Input: head = [1,2,3,3,4,4,5]
 *  Output: [1,2,5]
 *
 * Example 2:
 *  Input: head = [1,1,1,2,3]
 *  Output: [2,3]
 *
 * Constraints:
 *  The number of nodes in the list is in the range [0, 300].
 *  -100 <= Node.val <= 100
 *  The list is guaranteed to be sorted in ascending order.
 */
public class Num_0082 implements LeetCode {
    private interface Solution extends LinkedList {
        ListNode deleteDuplicates(ListNode head);

        default void assertExpected(int[] head, int[] expected) {
            if (!assertEquals(deleteDuplicates(build(head)), build(expected))) {
                deleteDuplicates(build(head));
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public ListNode deleteDuplicates(ListNode head) { // 未建立辅助头节点（复杂）：时O(n) 空O(1)
            /*
             * 删除顺序链表中存在重复的元素，仅保留原先无重复的元素
             * - [!] 注意：不是去重
             * - 若后一个与前一个相同，则删除
             */
            ListNode prev = null;
            ListNode cur = head;
            ListNode after;
            while (cur != null) {
                if (cur.next != null && cur.val == cur.next.val) { // 存在以 cur 开头的后续元素重复
                    after = cur.next;
                    while (after.next != null && after.next.val == cur.val) { // 寻找最后一个与 cur 重复的元素
                        after = after.next;
                    }
                    if (prev == null) {
                        head = after.next;
                        cur = head;
                    } else {
                        prev.next = after.next;
                        cur = prev.next;
                    }
                } else { // 无重复时
                    prev = cur;
                    cur = cur.next;
                }
            }
            return head;
        }
    }

    private static class MyHeaderSolution implements Solution {

        @Override
        public ListNode deleteDuplicates(ListNode head) { // 最优：建立辅助头节点：时O(n) 空O(1)
            /*
             * 删除顺序链表中存在重复的元素，仅保留原先无重复的元素
             * - [!] 注意：不是去重
             * - 若后一个与前一个相同，则删除
             * - prev 与 cur 之间存在多个间距
             *  prev -> 0
             *          1
             *          1
             *  cur  -> 1
             *          2
             */
            ListNode header = new ListNode(-1, head); // 建立辅助头节点
            ListNode prev = header;
            ListNode cur = prev.next;
            while (cur != null) {
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                if (prev.next == cur) { // 无重复时正常后移 <= prev 与 cur 之间无间距的情况
                    prev = cur;
                } else {
                    prev.next = cur.next; // 剪除重复区间，prev 不动 <= prev 与 cur 之间有间距的情况
                }
                cur = cur.next;
            }
            return header.next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MyHeaderSolution();
        solution.assertExpected(new int[]{1,2,3,3,4,4,5}, new int[]{1,2,5});
        solution.assertExpected(new int[]{1,1,1,2,3}, new int[]{2,3});
        solution.assertExpected(new int[]{1,1}, new int[]{});
    }
}
